#        Arvore de Usuarios       /\
#                                //\\
#  Grupo: Gustavo Pereira       ///\\\
#         Mario Fernandes      ////\\\\
#         Rafaella Leandra        ||

#VALOR = CPF DO USUARIO

class Nodo():
    def __init__(self, Valor, Pai=None, Esquerdo=None, Direito=None):
        self.Vermelho = True
        self.Dado = Valor
        self.Pai = Pai
        self.Esquerdo = Esquerdo
        self.Direito = Direito
        self.Sacola = [] #Limite de livros na Sacola

    def Nodo_vermelho(self): #pergunta True False
        return self.Vermelho
    
    def setPreto(self):
        self.Vermelho = False
    
    def setVermelho(self):
        self.Vermelho = True
    
    def getAvo(self):
        if self.Pai == None:
            return None
        else:
            return self.Pai.Pai
    
    def getPai(self):
        return self.Pai

    def getTio(self):
        if self.getAvo() != None:
            if self.getPai() == self.getAvo().Direito:
                return self.getAvo().Esquerdo #Tio
            elif self.getPai() == self.getAvo().Esquerdo:
                return self.getAvo().Direito
            else:
                return None

    def printCOR(self):
        if self.Vermelho == True:
            return "VERMELHO"
        else:
            return "PRETO"
         
#------------------------------------- Funcoes do EMPRESTIMO
    def Adicionar_livro_na_sacola(self,livro): 
        self.Sacola.append(livro)
        
    def Remover_livro_da_sacola(self,livro): 
        self.Sacola.remove(livro)
        
    def Sacola_cheia(self): #Pergunta
        if len(self.Sacola) < 3:
            return False
        else:
            return True
#------------------------------------- Funcoes do EMPRESTIMO

    def isLeft(self): #isleft
        if self.Pai == None: #RAIZ nao tem pai e irmao
            return None
        if self.Pai.Esquerdo != None: 
            return self.Pai.Esquerdo.Dado == self.Dado
        return False

class AVP_Usuario():
    def __init__(self):
        self.Raiz = None
        
    def Pesquisar(self, No, Valor): #interativo
        while No != None and Valor != No.Dado:
            if Valor < No.Dado:
                No = No.Esquerdo
            else: 
                No = No.Direito
        return No

    def Inserir(self, Valor):
        if self.Raiz == None:
            self.Raiz = Nodo(Valor)
            self.Raiz.setPreto()
            return
        self.Adicionar(Valor,self.Raiz)

    def Adicionar(self, Valor, No = None): 
        if Valor < No.Dado:                         #Adicionar na Esquerda
            if No.Esquerdo == None:
                V = Nodo(Valor, Pai=No)
                No.Esquerdo = V
                self.Inserir_FIX(V) 
            else:
                self.Adicionar(Valor, No.Esquerdo)
        elif Valor > No.Dado:                       #Adicionar na Direita
            if No.Direito == None:
                V = Nodo(Valor, Pai=No)
                No.Direito = V
                self.Inserir_FIX(V) 
            else:
                self.Adicionar(Valor, No.Direito)
        else:
            print("\nUsuario Ja cadastrado com esse CPF")
                                                            
    def Inserir_FIX(self, No):
        if No.Pai == None:
            No.setPreto()
            return
        
        if not No.Pai.Nodo_vermelho():
            return
        
        if No.getTio() != None and No.getTio().Nodo_vermelho():
            No.getTio().Vermelho = False
            No.Pai.Vermelho = False
            self.Inserir_FIX(No.getAvo())
            return
        self.Rotacionar(No) 

    def Rotacionar(self, No):  
        if No.isLeft():
            if No.Pai.isLeft(): 
                self.Rotacionar_Direita(No.Pai, False)
            else:
                self.Rotacionar_Esquerda(No, True)
        else:                                   
            if No.Pai.isLeft():
                self.Rotacionar_Direita(No, True)
            else:                               
                self.Rotacionar_Esquerda(No.Pai, False)
            

    def Rotacionar_Esquerda(self, No, Girar=False): 
        A = No
        B = A.Pai
        if Girar == True:
            C = A.Pai
            B = C.Pai
            B.Direito = A
            A.Pai = B
            C.Esquerdo = A.Direito
            if A.Direito != None:
                A.Direito.Pai = C
            A.Direito = C
            C.Pai = A
        D = B.Pai
        E = B.isLeft()    
        B.Direito = A.Esquerdo
        if B.Direito != None:
            B.Direito.Pai = B
        A.Esquerdo = B
        B.Pai=A
        B.setVermelho()
        A.setPreto()
        if D == None:
            A.Pai = None
            self.Raiz = A
        elif D != None and E:
            A.Pai=D
            D.Esquerdo=A
            D.setVermelho()
            self.Inserir_FIX(D)
        else:
            A.Pai=D
            D.Direito=A
            D.setVermelho()
            self.Inserir_FIX(D)

    def Rotacionar_Direita(self, No, Girar=False): 
        A = No
        B = A.Pai
        if Girar == True:
            C = A.Pai    
            B = C.Pai
            C.Direito = A.Esquerdo
            if A.Esquerdo != None:
                C.Direito.Pai = C
            B.Esquerdo = A
            A.Pai = B
            A.Esquerdo = C
            C.Pai = A
                
        D = B.Pai
        E = B.isLeft()
        B.Esquerdo = A.Direito
        if A.Direito != None:
            A.Direito.Pai = B
        A.Direito = B
        B.Pai = A
        B.setVermelho()
        A.setPreto()
        if D == None:
            A.Pai = None
            self.Raiz = A
        elif D != None and E:
            A.Pai = D
            D.Esquerdo = A
            D.setVermelho()
            self.Inserir_FIX(D)
        else:
            A.Pai = D
            D.Direito = A
            D.setVermelho()
            self.Inserir_FIX(D)
            
    def Imprimir_Arvore(self, No=None): #NA ORDEM
        No2=No
        if No == None:
            No2 = self.Raiz
        if No2.Esquerdo != None:
            self.Imprimir_Arvore(No2.Esquerdo)
        print "%s (%s)" %(No2.printCOR(),No2.Dado)
        if No2.Direito != None:
            self.Imprimir_Arvore(No2.Direito)        


#ARVORE=AVP_Usuario()
#ARVORE.Inserir(1)
#ARVORE.Inserir(2)
#ARVORE.Inserir(3)
#ARVORE.Inserir(4)
#ARVORE.Inserir(5)
#ARVORE.Inserir(6)
#ARVORE.Inserir(7)
#ARVORE.Inserir(8)
#ARVORE.Inserir(9)
#ARVORE.Inserir(10)
#ARVORE.Inserir(11)
#ARVORE.Imprimir_Arvore()
